#洛谷十月月赛 T2
题目背景
小强和阿米巴是好朋友。
题目描述
小强喜欢数列。有一天，他心血来潮，写下了三个长度均为n的数列。
阿米巴也很喜欢数列。但是他只喜欢其中一种，波动数列。
阿米巴把他的喜好告诉了小强。小强便打算找出这三个数列内的最长波动数列。
也就是说，如果我们将三个数列记做a[n][3]，他必须要构造一个二元组序列：，使得对于任何 i>1 有：
p[i] > p[i-1]
若q[i] = 0，a[p[i]][q[i]] >= a[p[i-1]][q[i-1]]
若q[i] = 1，a[p[i]][q[i]] <= a[p[i-1]][q[i-1]]
若q[i] = 2，只要保持段内同向即可（就是对于连续的一段q[i]=2，要么都有a[p[i]][q[i]] >= a[p[i-1]][q[i-1]]，要么都有a[p[i]][q[i]] <= a[p[i-1]][q[i-1]]）。
小强希望这个二元组序列尽可能长。
提示：当q[i] != q[i-1]时，数列的增减性由q[i]而非q[i-1]决定。
清晰版题目描述
小强拿到一个3×n的数组，要在每一列选一个数（或者不选），满足以下条件：
1.如果在第一行选，那它必须大于等于上一个数
2.如果在第二行选，那么必须小于等于上一个数
3.如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）
输入输出格式
输入格式：
输入包含4行。
第一行一个数n，表示数列长度。
第2、3、4行，每行n个整数，分别表示三个数列。
输出格式：
输出仅包含一个整数，即最长波动数列的长度。
输入输出样例
输入样例#1：
6
1 2 3 6 5 4
5 4 3 7 8 9
1 2 3 6 5 4
输出样例#1：
6
说明
对于20%的数据，n <= 10， m <= 1000
对于60%的数据，n <= 1000, m <= 1000
对于100%的数据， n <= 100000， m <= 1000000000
其中m = max|a[i]|
样例解释：
取第三行1 2 3（增），然后取第1行6（增），然后取第三行5 4（减），长度为6。
Solution
首先60分就是普通的区间dp.
分四种情况转移即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> using namespace std; inline int read(){ int rtn=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))rtn=(rtn<<1)+(rtn<<3)+ch-'0',ch=getchar(); return rtn*f; } int a[100010][4],dp[100010][4],ans=-1; int main() { int n=read(); for(int i=1;i<=n;i++)a[i][0]=read(); for(int i=1;i<=n;i++)a[i][1]=read(); for(int i=1;i<=n;i++)a[i][2]=read(),a[i][3]=a[i][2]; for(int i=1;i<=n;i++){ dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=1; for(int j=i-1;j;j--){ for(int k=0;k<4;k++){ if(a[i][0]>=a[j][k])dp[i][0]=max(dp[i][0],dp[j][k]+1); if(a[i][1]<=a[j][k])dp[i][1]=max(dp[i][1],dp[j][k]+1); if(a[i][2]<=a[j][k]&&k!=3)dp[i][2]=max(dp[i][2],dp[j][k]+1); if(a[i][3]>=a[j][k]&&k!=2)dp[i][3]=max(dp[i][3],dp[j][k]+1); } } ans=max(ans,max(dp[i][0],max(dp[i][1],max(dp[i][2],dp[i][3])))); } printf("%d",ans); return 0; }
|
由60分的dp可知
前两个转移方程只需要从前面的状态中找一个满足条件的即可
后两个转移方程中则需要保证转移时对方不能参与(严格单调)
那么我想想如何减少复杂度
首先我们可以先将权值离散化
即可将下标作为比较的键值
自然联想到将整个体系放入线段树中维护:
1.query(1,a[i])表示小于a[i]的状态可以转移
2.query(a[i],limit)表示大于a[i]的状态可以转移
由于后两个转移的影响,我们需要维护两颗线段树,保证这两颗线段树中彼此不会出现
对于前两个转移,只需要在两颗线段树中取最大值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> using namespace std; inline int read(){ int rtn=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))rtn=(rtn<<1)+(rtn<<3)+ch-'0',ch=getchar(); return rtn*f; } int a[100010][4],dp[100010][4],ans=-1,num[400010],tot; struct SegmentTree{ int maxn[2500010]; void update(int p,int l,int r,int pos,int c){ if(l==r){ maxn[p]=max(maxn[p],c); return; } int mid=(l+r)>>1; if(pos<=mid)update(p<<1,l,mid,pos,c); else if(pos>mid)update(p<<1|1,mid+1,r,pos,c); maxn[p]=max(maxn[p<<1],maxn[p<<1|1]); } int query(int p,int l,int r,int ql,int qr){ if(l==ql&&r==qr)return maxn[p]; int mid=l+r>>1; if(qr<=mid)return query(p<<1,l,mid,ql,qr); else if(ql>mid)return query(p<<1|1,mid+1,r,ql,qr); else return max(query(p<<1,l,mid,ql,mid),query(p<<1|1,mid+1,r,mid+1,qr)); } }S,T; int main() { int n=read(); for(int i=1;i<=n;i++)a[i][0]=read(),num[++tot]=a[i][0]; for(int i=1;i<=n;i++)a[i][1]=read(),num[++tot]=a[i][1]; for(int i=1;i<=n;i++)a[i][2]=read(),a[i][3]=a[i][2],num[++tot]=a[i][2]; sort(num+1,num+1+tot); tot=unique(num+1,num+1+tot)-num-1; for(int i=1;i<=n;i++) for(int j=0;j<4;j++) a[i][j]=lower_bound(num+1,num+1+tot,a[i][j])-num; for(int i=1;i<=n;i++){ dp[i][0]=max(S.query(1,1,tot,1,a[i][0]),T.query(1,1,tot,1,a[i][0]))+1; dp[i][1]=max(S.query(1,1,tot,a[i][1],tot),T.query(1,1,tot,a[i][1],tot))+1; dp[i][2]=S.query(1,1,tot,1,a[i][2])+1; dp[i][3]=T.query(1,1,tot,a[i][3],tot)+1; S.update(1,1,tot,a[i][0],dp[i][0]);T.update(1,1,tot,a[i][0],dp[i][0]); S.update(1,1,tot,a[i][1],dp[i][1]);T.update(1,1,tot,a[i][1],dp[i][1]); S.update(1,1,tot,a[i][2],dp[i][2]);T.update(1,1,tot,a[i][3],dp[i][3]); ans=max(ans,max(max(dp[i][1],dp[i][0]),max(dp[i][2],dp[i][3]))); } printf("%d",ans); }
|
